Vấn đề chúng ta đang cố gắng giải quyết là: cho trước một hợp số lẻ N, tìm một số nguyên d giữa 1 và N, là ước N. Chúng ta chỉ quan tâm đến giá trị N lẻ bởi vì nếu N chẵn thì hiển nhiên một ước nguyên tố của nó phải là 2. Hơn nữa, để thuật toán làm việc hiệu quả, ta cần N không phải lũy thừa của một số nguyên tố. Điều này có thể kiểm tra bằng cách kiểm tra xem N k {\displaystyle {\sqrt[{k}]{N}}} có phải là số nguyên hay không, với mọi k ≤ log 2 ⁡ ( N ) {\displaystyle k\leq \log _{2}(N)} .

Sau khi hai điều kiện trên thỏa mãn, ta đã có N là tích của hai số nguyên tố lẻ phân biệt. Theo định lý Thặng dư Trung Hoa, 1 có ít nhất 4 nghiệm phân biệt theo mod N, trong đó 1 và -1 là hai nghiệm tầm thường. Mục đích của thuật toán là tìm ra thành phần nghiệm b còn lại (b2 đồng dư với 1 theo mod N) từ đó dẫn đến phân tích nhân tử N bằng sàng bậc 2.

Nhưng ta có thể đơn giản việc tìm b bằng cách tìm một thành phần a (ta sẽ trình bày rõ hơn ở dưới). Các thuật toán lượng tử được dùng để lựa chọn ngẫu nhiên số a đó thay cho phải tìm kiếm tuần tự như các phương pháp tính toán cổ điển.

Thuật toán Shor có hai phần:

1. Sử dụng thuật toán Miller, đưa bài toán về bài toán tìm kiếm tuần tự.

2. Sử dụng thuật toán lượng tử để giải quyết bài toán tìm kiếm tuần tự đó.

Cụ thể, trong thuật toán Shor, thực hiện lại hầu hết các bước của thuật toán Miller bằng tính toán cổ điển (1), ngoại trừ một bước có độ phức tạp cao nhất (2).

Bước 1:Thuật toán Miller cổ điển gồm các bước sau:

• Chọn một số ngẫu nhiên a < N.
• Tìm ƯCLN(a, N), có thể dùng thuật toán Ơclit cho bước này.
• Nếu ƯCLN(a, N) ≠ 1, thì p = ƯCLN(a, N) và q = N / p.
• Nếu không thì tìm chu kỳ r của hàm f(x) = ax mod N, tức là f(x+r) = f(x).
• Nếu r lẻ, thì quay lại bước đầu tiên.
• Nếu a r /2 ≡ −1 (mod N), thì quay lại bước đầu tiên.
• p = ƯCLN(ar/2 + 1, N) và q = ƯCLN(ar/2 - 1, N).

Bước 2:Trong thuật toán Miller, bước có độ phức tạp cao nhất là bước tìm chu kỳ r của hàm f(x). Để tìm chu kỳ của một hàm số, có thể biến đổi Fourier hàm số này, khi đó kết quả biến đổi Fourier sẽ cực đại tại các giá trị k/r với k là các số nguyên. Biến đổi Fourier có thể thực hiện nhanh hơn trong tính toán lượng tử, như đã trình bày ở mục bên trên. Do đó bước này có thể được thực hiện bằng tính toán lượng tử như sau.

Cụ thể, hàm f(x) làm hàm tuần hoàn có thể nhận tối đa N giá trị, và có thể được biểu diễn bằng Q bit, với Q là số nguyên nhỏ nhất lớn hơn lôgarit cơ số 2 của N. Có thể thiết lập một hệ vật lý gồm hai thanh ghi cạnh nhau, mỗi thanh gồm Q qubit, và thực hiện:

i) Khởi tạo thanh ghi thứ nhất, còn thanh ghi thứ hai ở trạng thái nghỉ (trạng thái năng lượng thấp nhất, thường ứng với qubit |0>). Trạng thái của hệ 2 thanh ghi sau bước này là:

Q − 1 / 2 ∑ x = 0 Q − 1 | x ⟩ | 0 ⟩ {\displaystyle Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle \,}

ii) Xây dựng hàm f(x) thành toán tử lượng tử để áp dụng và hệ 2 thanh ghi sau bước trên, và thu được trạng thái mới của hệ là

Q − 1 / 2 ∑ x | x , f ( x ) ⟩ {\displaystyle Q^{-1/2}\sum _{x}\left|x,f(x)\right\rangle \,}

iii) Áp dụng biến đổi Fourier vào hệ.Với ω = e 2 π i Q {\displaystyle \omega =e^{\frac {2\pi i}{Q}}} , Lấy y là một trong r số nguyên dương mod N sao cho y.r/Q là số nguyên, ta có: U Q F T | x ⟩ = Q − 1 2 ∑ y ω x y | y ⟩ . {\displaystyle U_{QFT}\left|x\right\rangle =Q^{-{\frac {1}{2}}}\sum _{y}\omega ^{xy}\left|y\right\rangle .}

Điều này dẫn đến trạng thái cuối:

Q − 1 ∑ x ∑ y ω x y | y , f ( x ) ⟩ . {\displaystyle Q^{-1}\sum _{x}\sum _{y}\omega ^{xy}\left|y,f(x)\right\rangle .}

Ta viết lại tổng trên dưới dạng:

Q − 1 ∑ z ∑ y | y , z ⟩ ∑ x : f ( x ) = z ω x y . {\displaystyle Q^{-1}\sum _{z}\sum _{y}\left|y,z\right\rangle \sum _{x:\,f(x)=z}\omega ^{xy}.}

Đây là một sự chồng chập của nhiều hơn Q trạng thái rất nhiều nhưng ít hơn rất nhiều so với Q2, từ đó suy ra có ít hơn Q giá trị phân biệt z = f(x). Lấy:

• ω = e 2 π i Q {\displaystyle \omega =e^{\frac {2\pi i}{Q}}} là phương vị thứ Qth
• r la chu kì của hàm f
• x0 là giá trị nhỏ nhất của x thỏa mãn f(x) = z (ta có x0 < r)
• b xác định theo x, mà khi chạy từ 0 tới ⌊ ( Q − x 0 − 1 ) / r ⌋ {\displaystyle \lfloor (Q-x_{0}-1)/r\rfloor } ta có x 0 + r b < Q . {\displaystyle x_{0}+rb<Q.} .

ω r y {\displaystyle \omega ^{ry}} là một vecto đơn vị trong mặt phẳng phức (trong đó ω {\displaystyle \omega } là căn đơn vị và r, y là các số nguyên dương), thì hệ số Q 1 | y , z ⟩ {\displaystyle Q^{1}\left|y,z\right\rangle } trong trạng thái cuối là:

∑ x : f ( x ) = z ω x y = ∑ b ω ( x 0 + r b ) y = ω x 0 y ∑ b ω r b y . {\displaystyle \sum _{x:\,f(x)=z}\omega ^{xy}=\sum _{b}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b}\omega ^{rby}.}

iv) Thực hiện phép đo, để trạng thái của hệ hai thanh ghi sụp về một trong các trạng thái riêng. Thanh ghi thứ nhất sụp về trạng thái ứng với chuỗi nhị phân thể hiện giá trị s, trong đó xác suất để s là bội số của 1/r là cao.

| Q − 1 ∑ x : f ( x ) = z ω x y | 2 = Q − 2 | ∑ b ω ( x 0 + r b ) y | 2 = Q − 2 | ∑ b ω b r y | 2 . {\displaystyle \left|Q^{-1}\sum _{x:\,f(x)=z}\omega ^{xy}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{(x_{0}+rb)y}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{bry}\right|^{2}.}

v) Thử lại, bằng tính toán cổ điển, xem nếu f(x) = f(x + 1/s) thì kết thúc

vi) Nếu không thì thử, bằng tính toán cổ điển, với các giá trị là 1/sk với các k nguyên khác nhau, nếu một trong các giá trị này thỏa mãn thì kết thúc.

vii) Nếu không thì lặp lại từ bước đầu tiên